package offer.yuanFuDao;

import java.util.Arrays;

/**
 * 排序
 * @author DengYuan2
 * @create 2021-02-27 19:37
 */
public class NC140 {
    public static void main(String[] args) {
        NC140 n = new NC140();
        int[] arr= {5,2,3,1,4};
//        int[] res = n.quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(res));
//        int [] tmp = new int[arr.length];
//        int[] res = n.mergeSort(arr, 0, arr.length - 1, tmp);
//        System.out.println(Arrays.toString(res));
        int[] res = n.heapSort(arr);
        System.out.println(Arrays.toString(res));


    }


    public int[] MySort (int[] arr) {

        return arr;
    }

    /**
     * 冒泡排序
     * @param arr
     * @return
     */
    public int[] bubbleSort(int[] arr){
        int len = arr.length;
        boolean flag=false;
        for (int i = 0; i < len-1; i++) {
            flag=false;
            for (int j = 0; j < len-i-1; j++) {
                if (arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    flag=true;
                }
            }
            if (!flag){
                break;
            }
        }
        return arr;
    }

    /**
     * 选择排序
     * @param arr
     * @return
     */
    public int[] selectSort(int[] arr){
        int len =arr.length;
        for (int i = 0; i < len-1; i++) {
            int min =arr[i];
            int minIdx = i;
            for (int j = i+1; j < len; j++) {
                if (arr[j]<min){
                    min=arr[j];
                    minIdx=j;
                }
            }
            if (minIdx!=i){
                arr[minIdx]=arr[i];
                arr[i]=min;
            }
        }
        return arr;
    }

    /**
     * 插入排序
     * @param arr
     * @retur\
     * i76
     */
    public int[] insertSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int idx=i-1;
            int cur = arr[i];
            while (idx>=0 && cur< arr[idx]) {
                arr[idx+1]=arr[idx];
                idx--;
            }
            if (idx+1!=i){
                arr[idx+1]=cur;
            }
        }
        return arr;
    }

    /**
     * 希尔排序
     * @param arr
     * @return
     */
    public int[] shellSort(int[] arr){
        int len =arr.length;
        for (int gap = len/2; gap >=1 ; gap/=2) {
            for (int i = gap; i < len; i++) {
                int insertValue = arr[i];
                int insertIdx = i;
                int pre = insertIdx-gap;
                while (pre>=0&&arr[pre]>insertValue){
                    arr[pre+gap]=arr[pre];
                    pre-=gap;
                }
                if (pre+gap!=insertIdx){
                    arr[pre+gap]=insertValue;
                }
            }

        }

        return arr;
    }

    /**
     * 快速排序
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public int[] quickSort(int[] arr,int l,int r){
        int left =l;
        int right=r;
        if (l<r){
            int tmp = arr[left];
            while (left!=right){
                while (left<right&&arr[right]>tmp){
                    right--;
                }
                if (left<right){
                    arr[left]=arr[right];
                    left++;
                }
                while (left<right&&arr[left]<tmp){
                    left++;
                }
                if (left<right){
                    arr[right]=arr[left];
                    right--;
                }
            }
            arr[left]=tmp;
            quickSort(arr,l,left-1);
            quickSort(arr,left+1,r);
        }

        return arr;
    }

    /**
     * 归并排序
     * @param arr
     * @param left
     * @param right
     * @param tmp
     * @return
     */
    public int[] mergeSort(int[] arr,int left,int right,int[] tmp){
        if (left<right){
            int mid = (left+right)/2;
            mergeSort(arr,left,mid,tmp);
            mergeSort(arr,mid+1,right,tmp);
            merge(arr,left,mid,right,tmp);
        }
        return arr;
    }

    public void merge(int[] arr,int left,int mid,int right,int[] tmp){
        int l = left;
        int r =mid+1;
        int idx = 0;
        while (l<=mid&&r<=right){
            if (arr[l]<arr[r]){
                tmp[idx++]=arr[l++];
            }else {
                tmp[idx++]=arr[r++];
            }
        }
        while (l<=mid){
            tmp[idx++]=arr[l++];
        }
        while (r<=right){
            tmp[idx++]=arr[r++];
        }
        //
        idx=0;
        for (int i = left; i <= right; i++) {
            arr[i]=tmp[idx++];
        }

    }

    public int[] heapSort(int[] arr){
        for (int i = arr.length/2-1; i >=0; i--) {
            adjustHeap(arr,i,arr.length);
        }
        for (int i = arr.length-1; i >0; i--) {
            int tmp =arr[0];
            arr[0]=arr[i];
            arr[i]=tmp;
            adjustHeap(arr,0,i);
        }
        return arr;
    }

    public void adjustHeap(int[] arr,int start,int length){
        int k = 2*start+1;
        int tmp = arr[start];
        for (;k<length;k=k*2+1){
            if (k+1<length && arr[k]<arr[k+1]){
                k++;
            }
            if (arr[k]>tmp){
                arr[start]=arr[k];
                start=k;
            }else {
                break;
            }
        }
        arr[start]=tmp;
    }
}
